import avl.AVLNode;
import avl.AVLTree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 26
 * Time:17:39
 */
public class Main {
    public static void main(String[] args) {
        //test1();
        test2();
    }

    private static void test2() {
        for (int i = 0; i < 10; i++) {
            Random random = new Random();
            AVLTree tree = new AVLTree();
            for (int j = 0; j < 1_0000; j++) {
                int key = random.nextInt(1_0000);
                tree.insert(key);
            }
            validate(tree);
        }
    }

    /***
     * 验证是否是搜索树和平衡树
     * @param tree
     */
    private static void validate(AVLTree tree) {
        validateIsSearchTree(tree);
        validateIsBalanceTree(tree);
        System.out.println("这棵树是一棵AVL树！");
    }

    private  static int heightAndCheckBF(AVLNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = heightAndCheckBF(root.left);
        int rightHeight = heightAndCheckBF(root.right);

        if(root.bf != (leftHeight - rightHeight)){
            throw  new RuntimeException("有节点bf计算不正确！");
        }

        if(root.bf != -1 && root.bf != 0 && root.bf != 1){
            throw  new RuntimeException("有节点，左右子树的高度差绝对值超过了1，不是平衡树！");
        }
        return Integer.max(leftHeight,rightHeight) + 1;
    }
    /***
     * 验证是否是二叉平衡树——只要保证每个节点的平衡因子在{-1,0,1}
     * @param tree
     */
    private static void validateIsBalanceTree(AVLTree tree) {
        heightAndCheckBF(tree.root);
        System.out.println("所有的节点的bf计算正确，并且都在{-1,0,1}范围内，是平衡树！");
    }

    /***
     * 验证是否是搜索树——只要中序遍历有序即可
     * @param tree
     */
    private static void validateIsSearchTree(AVLTree tree) {
        List<Long> inorderKeys = new ArrayList<>();
        inorderSaveKey(inorderKeys,tree.root);
        //inorderKeys中保存中序遍历后的所有key

        //复制出得到所有的key ，对得到的key进行排序
        List<Long> keySorted = new ArrayList<>(inorderKeys);
        Collections.sort(keySorted);

        if(keySorted.equals(inorderKeys)){
            System.out.println("中序遍历是有序的，说明此树是一棵搜索树！");
        }else{
            throw  new RuntimeException("中序遍历是无序的，不是一棵搜索树！");
        }
    }

    /***
     * 中序遍历
     * @param inorderKeys
     * @param root
     */
    private static void inorderSaveKey(List<Long> inorderKeys, AVLNode root) {
        if(root != null){
            inorderSaveKey(inorderKeys,root.left);
            inorderKeys.add(root.key);
            inorderSaveKey(inorderKeys,root.right);
        }
    }

    private static void test1() {
        List<Integer> list = Arrays.asList(2,15,8,3,4,6,9,7,17,20,19,14);

        AVLTree tree = new AVLTree();
        for(Integer key:list){
            tree.insert(key);
        }
        preorder(tree.root);
        System.out.println();
        inorder(tree.root);
        System.out.println();

    }

    /***
     * 前序遍历
     * @param node
     */
    private static  void preorder(AVLNode node){
        if(node != null){
            System.out.println(node.key + "," + node.bf);
            preorder(node.left);
            preorder(node.right);
        }
    }

    /***
     * 中序遍历
     * @param node
     */
    private static  void inorder(AVLNode node){
        if(node != null){
            inorder(node.left);
            System.out.println(node.key + "," + node.bf);
            inorder(node.right);
        }
    }
}
